package loengud.w10;

import java.util.Arrays;

public class Sorting {

	public static void main(String[] args) {
		int[] a = { 4, 5, 8, 7, 1, 9, 2, 3, 6 };
		insertionSort(a);
		System.out.println(Arrays.toString(a));
		int[] b = { 4, 5, 8, 7, 1, 9, 2, 3, 6 };
		mergesort(b);
		System.out.println(Arrays.toString(b));
		int[] c = { 4, 5, 8, 7, 1, 9, 2, 3, 6 };
		//int[] c = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		//int[] c = { 5, 4, 8, 7, 1, 6, 2, 3, 9 };
		quicksort(c, 0, c.length - 1);
		System.out.println(Arrays.toString(c));
		System.out.println("quicksortCount:" + quicksortCount);
	}

	public static void insertionSort(int[] A) {
		int itemsSorted; // Number of items that have been sorted so far.

		for (itemsSorted = 1; itemsSorted < A.length; itemsSorted++) {
			int temp = A[itemsSorted]; // The item to be inserted.
			int loc = itemsSorted - 1; // Start at end of list.
			while (loc >= 0 && A[loc] > temp) {
				A[loc + 1] = A[loc]; // Bump item from A[loc] to loc + 1
				loc = loc - 1; // Go on to next location.
			}

			A[loc + 1] = temp; // Put temp in last vacated space.
		} // -for
	}

	static void mergesort(int[] A) {
		if (A.length > 1) {
			// split the array into two pieces,
			// as close to the same size as possible.
			int[] first = extract(A, 0, A.length / 2);
			int[] last = extract(A, A.length / 2, A.length);

			// sort each of the two halves recursively
			mergesort(first);
			mergesort(last);

			// merge the two sorted halves together
			merge(A, first, last);
		} // -if
	}

	// extract: returns a subarray of A,
	// starting with index start in A,
	// continuing to (but not including) index last.

	static int[] extract(int[] A, int start, int last) {
		int[] ret = new int[last - start];

		for (int i = 0; i < ret.length; i++)
			ret[i] = A[start + i];

		return ret;
	}
	/*
	 * a                  b
	 * 1 3 5 7 9 12       2 4 6
	 * ^                  ^
	 * 
	 * ac < bc: 1
	 *   ^ 
	 * bc < ac: 2
	 *                      ^
	 *     ^
	 *                        ^
	 *                        
	 *       ^ ^ ^
	 * 1 2 3 4 5 6 7 9 12
	 *                        
	 */




	// merge: merges arrays a and b, placing the result into the
	// array dest. This only works if both a and b are already in
	// increasing order.
	static void merge(int[] dest, int[] a, int[] b) {
		int i = 0;
		int j = 0;

		while (i < a.length && j < b.length) {
			if (a[i] < b[j]) {
				dest[i + j] = a[i];
				++i;
			} else {
				dest[i + j] = b[j];
				++j;
			}
		} // -while

		for (; i < a.length; i++) dest[i + j] = a[i];
		for (; j < b.length; j++) dest[i + j] = b[j];
	}

	static int quicksortCount = 0;
	static void quicksort(int[] A, int lo, int hi) {
		System.out.print(Arrays.toString(A));
		System.out.println(" lo:" + lo + " hi:" + hi);
		quicksortCount++;
		
		if (hi <= lo) {
			// The list has length one or zero. Nothing needs
			// to be done, so just return from the subroutine.
			return;
		} else {
			// Apply quicksortStep and get the pivot position.
			// Then apply quicksort to sort the items that
			// precede the pivot and the items that follow it.
			int pivotPosition = quicksortStep(A, lo, hi);
			quicksort(A, lo, pivotPosition - 1);
			quicksort(A, pivotPosition + 1, hi);
		} // -else
	}

	static int quicksortStep(int[] A, int lo, int hi) {
		int pivot = A[lo]; // Get the pivot value

		while (hi > lo) {
			while (hi > lo && A[hi] > pivot)
				hi--;
			if (hi == lo)
				break;

			A[lo] = A[hi];
			lo++;

			while (hi > lo && A[lo] < pivot)
				lo++;
			if (hi == lo)
				break;

			A[hi] = A[lo];
			hi--;
		} // -while

		A[lo] = pivot;
		return lo;
	} // -quicksortStep

}
